package com.mlamp.字典树;

import java.util.Stack;

public class ExpressionUtils {
    public static void main(String[] args) {

        Stack od = new Stack();
        Stack op = new Stack();
        String input = "1-2+3*(4-5)";
        int index = 0;
        int length = input.length();
        while (index < length) {
            char c = input.charAt(index);
            //如果是左括号，直接入操作栈
            if (c == '(') {
                op.push(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                //如果是四则运算，判断当前操作符优先级跟操作栈栈顶操作符优先级哪个更高一些
                int curOpLevel = getOpLeavel(c);

                //循环获取操作栈栈顶操作符
                while (true) {
                    int stackTopLevel = 0;
                    //如果操作栈不空，取出栈顶操作符
                    if (!op.isEmpty()) {
                        Object object = op.peek();
                        stackTopLevel = getOpLeavel((char) object);
                    }

                    //如果当前操作优先级大于操作栈栈顶运算符优先级，直接入栈
                    if (curOpLevel > stackTopLevel) {
                        op.push(c);
                        break;
                    } else {
                        //如果栈顶运算符优先级更高，则进行计算并将操作结果入操作数栈
                        try {
                            char optemp = '0';
                            int odNumber1 = 0;
                            int odNumber2 = 0;
                            if (!op.isEmpty()) {
                                optemp = (char) op.pop();
                            }
                            if (!od.isEmpty()) {
                                odNumber1 = (int) od.pop();
                                odNumber2 = (int) od.pop();
                            }
                            od.push(calculate(optemp, odNumber2, odNumber1));
                        } catch (Exception ex) {
                            ex.printStackTrace();
                        }
                    }
                }
            } else if (c == ')') {
                //如果当前符号是右括号
                while (true) {
                    // 取出栈顶运算符
                    char theop = (char) op.pop();
                    // 如果是左括号，结束
                    if (theop == '(') break;

                    //否则使用操作栈顶操作运算符进行计算，操作结果进操作数栈
                    else {
                        try {
                            int odNumber1 = (int) od.pop();
                            int odNumber2 = (int) od.pop();
                            od.push(calculate(theop, odNumber2, odNumber1));
                        } catch (Exception ex) {
                            ex.printStackTrace();
                        }
                    }
                }
            } else if (c >= '0' && c <= '9') {
                // 如果是数字，截取数字部分，并入操作数栈
                int tempIndex = index + 1;
                while (tempIndex < length) {
                    char tempc = input.charAt(tempIndex);
                    if (tempc >= '0' && tempc <= '9') {
                        tempIndex++;
                    } else break;
                }
                String odStr = input.substring(index, tempIndex);
                try {
                    int odNum = Integer.parseInt(odStr);
                    od.push(odNum);
                    index = tempIndex - 1;
                } catch (Exception ex) {
                    ex.printStackTrace();
                }
            }
            index++;
        }
        // 如果操作栈还有待处理的操作，进一步操作
        while (true) {
            Object obj = null;
            if (!op.isEmpty()) {
                obj = op.pop();
            }
            if (obj == null) {
                break;
            } else {
                char optemp = (char) obj;
                int odNum1 = (int) od.pop();
                int odNum2 = (int) od.pop();
                od.push(calculate(optemp, odNum2, odNum1));
            }
        }
        int result = 0;
        try {
            // 返回栈顶元素
            result = (int) od.pop();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        System.out.println(result);
    }


    public static int calculate(char op, int od1, int od2) {
        switch (op) {
            case '+':
                return od1 + od2;
            case '-':
                return od1 - od2;
            case '*':
                return od1 * od2;
            case '/':
                return od1 / od2;
        }
        return 0;
    }


    public static int calculateA(char op, int od1, int od2) {
        switch (op) {
            case '+':
                return od1 + od2;
            case '-':
                return od1 - od2;
            case '*':
                return od1 * od2;
            case '/':
                return od1 / od2;
        }
        return 0;
    }

    public static int getOpLevel(char op) {
        switch (op) {
            case '(':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return 0;
        }
    }


    public static int getOpLeavel(char op) {
        switch (op) {
            case '(':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return 0;
        }
    }

}
